// https://leetcode.cn/problems/triangle/description/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用动态规划自顶向下计算最小路径和
// 2. 利用一维数组进行空间优化，从右向左更新避免覆盖
// 3. 边界情况特殊处理：最右只能从左上，最左只能从正上
// 4. 中间位置取正上和左上路径的最小值
// 5. 时间复杂度：O(N²)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
private:
    const int INF = 0x3f3f3f3f;
public:
    int minimumTotal(vector<vector<int>>& triangle) 
    {
        int m = triangle.size();

        vector<int> dp(m, INF);
        dp[0] = triangle[0][0];

        for (int i = 1 ; i < m ; i++)
        {
            for (int j = i ; j >= 0 ; j--)
            {
                if (j == i)
                {
                    dp[j] = dp[j - 1] + triangle[i][j];
                }
                else if (j == 0)
                {
                    dp[j] = dp[j] + triangle[i][j];
                }
                else
                {
                    dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j];
                }
            }
        }

        return *min_element(dp.begin(), dp.end());
    }
};

int main()
{
    vector<vector<int>> triangle1 = {{2}, {3,4}, {6,5,7}, {4,1,8,3}};
    vector<vector<int>> triangle2 = {{-10}};
    
    Solution sol;

    cout << sol.minimumTotal(triangle1) << endl;
    cout << sol.minimumTotal(triangle2) << endl;

    return 0;
}